class Solution {
public:
    bool backtracking(vector<vector<char>>& board, string word, int row, int col, int cnt)
    {
        if (row < 0 || col < 0 || row >= board.size() || col >= board[0].size() || board[row][col] != word[cnt])
        {
            return false;
        }

        if (cnt == word.size() - 1)
        {
            return true;
        }
        char tmp = board[row][col];
        board[row][col] = ' ';
        bool ans = (backtracking(board, word, row + 1, col, cnt + 1)
            || backtracking(board, word, row - 1, col, cnt + 1)
            || backtracking(board, word, row, col + 1, cnt + 1)
            || backtracking(board, word, row, col - 1, cnt + 1));
        board[row][col] = tmp;
        return ans;
    }
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                if (backtracking(board, word, i, j, 0))
                {
                    return true;
                }
            }
        }

        return false;
    }
};